﻿#ifndef __SHELL__
#define __SHELL__
//shell 相比插入排序，选择排序更先进
//虽然也是o(n*n), 但是对于较好的step 选择，能达到不错的使用性能
//下面实现中的step 是knuth 1969年提出的。比起1959年shell 本人提出的1,2,4,8,16...效率高出很多
//shell 的序列直到最后一步才对奇数位的元素进行比较排序，因此效率会很低
template <class item>
void shell(item arr[], int left, int right){
	int step;
	for(step = 1; step <= (right - left)/3; step = step*3+1);
	for(;step > 0; step /= 3){
		for(int i = left+step; i <= right; ++i){
			item key = arr[i];
			int j = i - step;
			for(;;){
				if(key >= arr[j] || j < left) break;
				arr[j+step] = arr[j];
				j -= step;
			}
			arr[j+step] = key;
		}
	}
}
#endif